// metadoc List copyright Steve Dekorte 2002
// metadoc List license BSD revised
/*metadoc List description
List is an array of void pointers.
The List is not responsible for io_freeing its elements.
*/

#ifdef LIST_C
#define IO_IN_C_FILE
#endif
#include "Common_inline.h"
#include "PortableSorting.h"
#ifdef IO_DECLARE_INLINES

#define LIST_FOREACH(list, index, value, code)                                 \
    {                                                                          \
        const List *foreachList = list;                                        \
        size_t index, foreachMax = foreachList->size;                          \
                                                                               \
        for (index = 0; index < foreachMax; index++) {                         \
            void *value = foreachList->items[index];                           \
            code;                                                              \
        }                                                                      \
    }

#define LIST_SAFEFOREACH(list, index, value, code)                             \
    {                                                                          \
        const List *foreachList = list;                                        \
        size_t index;                                                          \
                                                                               \
        for (index = 0; index < List_size(foreachList); index++) {             \
            void *value = List_at_(foreachList, index);                        \
            code;                                                              \
        }                                                                      \
    }

#define LIST_REVERSEFOREACH(list, index, value, code)                          \
    {                                                                          \
        const List *foreachList = list;                                        \
        size_t index = List_size(foreachList);                                 \
                                                                               \
        while (index) {                                                        \
            void *value = List_at_(foreachList, (index--));                    \
            code;                                                              \
        }                                                                      \
    }

#define LIST_SAFEREVERSEFOREACH(list, index, value, code)                      \
    {                                                                          \
        const List *foreachList = list;                                        \
        size_t index = List_size(foreachList);                                 \
                                                                               \
        for (index = List_size(foreachList) - 1; index > 0; index--) {         \
            void *value = List_at_(foreachList, index);                        \
            code;                                                              \
            if (index > List_size(foreachList) - 1) {                          \
                index = List_size(foreachList) - 1;                            \
            }                                                                  \
        }                                                                      \
    }

#define LIST_DO_(list, func)                                                   \
    {                                                                          \
        const List *foreachList = list;                                        \
        size_t index, foreachMax = List_size(foreachList);                     \
                                                                               \
        for (index = 0; index < foreachMax; index++) {                         \
            func(List_at_(foreachList, index));                                \
        }                                                                      \
    }

IOINLINE size_t List_size(const List *self) { return self->size; }

IOINLINE void List_ifNeededSizeTo_(List *self, size_t newSize) {
    if (newSize * sizeof(void *) >= self->memSize) {
        List_preallocateToSize_(self, newSize);
    }
}

IOINLINE void *List_rawAt_(List *self, size_t index) {
    return self->items[index];
}

IOINLINE void *List_at_(const List *self, ssize_t index) {

    /* Negative indexing is also supported. */
    if (index < 0) {
        index += self->size;
    }

    if (index < self->size) {
        return self->items[index];
    }

    return (void *)NULL;
}

// --------------------------------------------

IOINLINE size_t List_indexOf_(List *self, void *item) {
    LIST_FOREACH(self, i, v, if (v == item) return i);
    return -1;
}

IOINLINE int List_contains_(List *self, void *item) {
    LIST_FOREACH(self, i, v, if (v == item) return 1);
    return 0;
}

IOINLINE void *List_append_(List *self, void *item) {
    List_ifNeededSizeTo_(self, self->size + 1);
    self->items[self->size] = item;
    self->size++;
    return item;
}

IOINLINE void List_appendSeq_(List *self, const List *otherList) {
    LIST_FOREACH(otherList, i, v, List_append_(self, v));
}

IOINLINE void List_compactIfNeeded(List *self) {
    if (self->memSize > 1024 &&
        self->size * sizeof(void *) * 4 < self->memSize) {
        List_compact(self);
    }
}

IOINLINE void List_removeIndex_(List *self, size_t index) {
    if (index < self->size) {
        if (index != self->size - 1) {
            memmove(&self->items[index], &self->items[index + 1],
                    (self->size - 1 - index) * sizeof(void *));
        }

        self->size--;

        List_compactIfNeeded(self);
    }
}

IOINLINE void List_removeIndex_toIndex_(List *self, size_t index1,
                                        size_t index2) {
    size_t length;

    if (index1 > self->size - 1) {
        index1 = self->size - 1;
    }

    if (index2 > self->size - 1) {
        index2 = self->size - 1;
    }

    length = index2 - index1;

    if (length <= 0) {
        return;
    }

    memmove(&self->items[index1], &self->items[index2],
            (self->size - index2) * sizeof(void *));

    self->size -= length;

    List_compactIfNeeded(self);
}

IOINLINE void List_remove_(List *self, void *item) {
    size_t index;

    for (index = 0; index < self->size; index++) {
        if (self->items[index] == item) {
            List_removeIndex_(self, index);
        }
    }
}

IOINLINE int List_removeFirst_(List *self, void *item) {
    size_t i, max = self->size;

    for (i = 0; i < max; i++) {
        if (self->items[i] == item) {
            List_removeIndex_(self, i);
            return 1;
        }
    }

    return 0;
}

IOINLINE void List_removeLast_(List *self, void *item) {
    size_t index = self->size - 1;

    for (index = self->size - 1; index > -1; index--) {
        if (self->items[index] == item) {
            List_removeIndex_(self, index);
            break;
        }
    }
}

IOINLINE void List_removeItems_(List *self, List *other) {
    LIST_FOREACH(other, i, v, List_remove_(self, v));
}

IOINLINE void List_at_insert_(List *self, size_t index, void *item) {
    if (index > self->size - 1) {
        List_preallocateToSize_(self, index + 1);
    } else {
        List_ifNeededSizeTo_(self, self->size + 1);
    }

    memmove(&self->items[index + 1], &self->items[index],
            (self->size - index) * sizeof(void *));

    self->items[index] = item;
    self->size++;
}

IOINLINE void List_at_put_(List *self, size_t index, void *item) {
    List_ifNeededSizeTo_(self, index);
    self->items[index] = item;

    if (index + 1 > self->size) {
        self->size = index + 1;
    }
}

IOINLINE void List_swap_with_(List *self, long index1, long index2) {
    if (index1 < 0 || index2 < 0) {
        return;
    }

    if (index1 != index2) {
        void **items = self->items;
        register void *v1 = items[index1];

        items[index1] = items[index2];
        items[index2] = v1;
    }
}

IOINLINE void List_reverseInPlace(List *self) {
    register void **i = self->items;
    register void **j = i + (self->size - 1);
    register void *iv;

    while (j > i) {
        iv = *i;
        *i = *j;
        *j = iv;
        j--;
        i++;
    }
}

// stack --------------------------------------------------

IOINLINE void List_push_(List *self, void *item) {
    List_ifNeededSizeTo_(self, self->size + 1);
    self->items[self->size] = item;
    self->size++;
}

IOINLINE void *List_pop(List *self) {
    void *item;

    if (!self->size) {
        return (void *)NULL;
    }

    self->size--;
    item = self->items[self->size];
    List_compactIfNeeded(self);
    return item;
}

IOINLINE void *List_top(const List *self) {
    if (!self->size) {
        return (void *)NULL;
    }

    return self->items[self->size - 1];
}

/* --- perform -------------------------------------------------- */

IOINLINE int List_removeTrueFor_(List *self, ListCollectCallback *callback) {
    size_t getIndex = 0;
    size_t putIndex = 0;
    size_t count = self->size;
    void **items = self->items;

    while (getIndex < count) {
        void *item = items[getIndex];

        if (item && !((*callback)(item))) {
            if (getIndex != putIndex) {
                items[putIndex] = item;
            }

            putIndex++;
        }

        getIndex++;
    }

    self->size = putIndex;

    return (int)(getIndex - putIndex);
}

IOINLINE void List_qsort(List *self, ListSortCallback *callback) {
    qsort(self->items, self->size, sizeof(void *), *callback);
}

IOINLINE void List_qsort_r(List *self, void *context,
                           ListSortRCallback *callback) {
    portable_qsort_r(self->items, self->size, sizeof(void *), context,
                     *callback);
}

IOINLINE void *List_bsearch(List *self, const void *key,
                            ListSortCallback *callback) {
    return bsearch(key, self->items, self->size, sizeof(void *), callback);
}

IOINLINE void *List_first(const List *self) { return List_at_(self, 0); }

IOINLINE void *List_last(List *self) {
    return List_at_(self, List_size(self) - 1);
}

#undef IO_IN_C_FILE
#endif
